package com.pashanhoo.datastructure.leetcode;

/**
 * @author 胡庆安
 * @version V1.0
 * @Package com.pashanhoo.datastructure.leetcode
 * @date 2020/10/27 12:33
 * @Copyright © 2010-2020 爬山虎科技（扬州）股份有限公司
 */
//给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
//给定一个链表: 1->2->3->4->5, 和 n = 2.
//
//当删除了倒数第二个节点后，链表变为 1->2->3->5.
public class Test19 {
    public static void main(String[] args) {
        ListNode l2 = new ListNode(2);
        ListNode l1 = new ListNode(1);
        l1.next = l2;
        removeNthFromEnd(l1,2);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //首先明确目标，删除一个节点需要的到删除节点和该节点的前置节点

        //1.获取链表的长度
        ListNode temp = head.next;
        int size = 1;
        while (temp!=null){
            size++;
            temp = temp.next;
        }

        if (size == 1){
            return null;
        }

        //2.获取三个必要的节点
        int target = size - n + 1;
        int targetPre = size - n;
        temp = head;
        int count = 0;
        while (temp!=null){
            count++;
            if (count == targetPre){//到删除目标前一个时停下
                break;
            }
            temp = temp.next;

        }
        ListNode nextNode;
        //现在的temp时删除前一个
        if (temp != null){
            nextNode = temp.next == null? null:temp.next.next;
            temp.next = nextNode;

        }else {//这是删除的是头元素
            return head.next;
        }

        return head;
    }
}
